package day_03;

public class MaxHeap {
    private int capacity;
    private int[] data;
    private int count;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        count = 0;
    }

    public void insert(int k){
        assert (count + 1 <= capacity);
        data[count + 1] = k;
        count++;
        shiftUp(count);
    }

    public int extract(){
        assert (count > 0);
        int ret = data[1];
        swap(data, 1, count);
        count--;
        shiftDown(1);
        return ret;
    }

    private void shiftUp(int k) {
        while(k > 1 && data[k] > data[k/2]){
            swap(data, k, k/2);
            k /= 2;
        }
    }

    private void shiftDown(int k){
        while(2 * k <= count){
            int j = 2 * k; // 有左孩子
            if(j + 1 <= count && data[j+1] > data[j]){
                j++;
            }

            if(data[k] >= data[j]){
                break;
            }
            swap(data, j, k);
            k = j;
        }
    }

    private void swap(int[] data, int k, int i) {
        int tmp = data[k];
        data[k] = data[i];
        data[i] = tmp;
    }

    public int size(){
        return count;
    }

    public boolean isEmpty(){
        return count == 0;
    }

    public void printHeap(){
        for (int i = 1; i <= this.count; i++) {
            System.out.print(data[i] + " ");
        }
    }
}
